package lru;

import java.util.HashMap;

/**
 * leet-code(146) LRU 缓存机制
 *
 * @author Ringo
 * @date 2021/10/9 22:02
 */
@SuppressWarnings("AlibabaClassNamingShouldBeCamel")
public class LRUCache {

    /**
     * key -> LinkedNode(key, val)
     */
    private HashMap<Object, LinkedNode> map;

    /**
     * 双向链表
     */
    private DoubleList cache;

    /**
     * 最大容量
     */
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public Object get(Object key) {
        if (!map.containsKey(key)) {
            return null;
        }
        Object val = map.get(key).val;
        // 利用 put 方法将该数据提前
        put(key, val);
        return val;
    }

    public void put(Object key, Object value) {
        LinkedNode x = new LinkedNode(key, value);
        if (map.containsKey(key)) {
            cache.remove(map.get(key));
        } else {
            if (capacity == cache.size()) {
                LinkedNode last = cache.removeLast();
                map.remove(last.key);
            }
        }
        cache.addFirst(x);
        map.put(key, x);
    }

    public static LRUCache create(int capacity) {
        return new LRUCache(capacity);
    }

    /**
     * 双向链表结点
     */
    public static class LinkedNode {
        public Object key, val;
        public LinkedNode prev, next;

        public LinkedNode(Object key, Object val) {
            this.key = key;
            this.val = val;
        }
    }

    /**
     * 双向链表
     */
    public static class DoubleList {

        private LinkedNode head, tail;

        private int size;

        /**
         * 在链表头部添加节点 x
         *
         * @param x 要添加的结点
         */
        public void addFirst(LinkedNode x) {
            if (head == null) {
                head = x;
                tail = x;
            } else {
                LinkedNode n = head;
                n.prev = x;
                x.next = n;
                head = x;
            }
            ++size;
        }

        /**
         * 删除链表中的 x 节点（x 一定存在）
         *
         * @param x 要删除的结点
         */
        public void remove(LinkedNode x) {
            if (head == x && tail == x) {
                head = null;
                tail = null;
            } else if (tail == x) {
                tail = x.prev;
                x.prev.next = null;
                x.prev = null;
            } else if (head == x) {
                head = x.next;
                x.next.prev = null;
                x.next = null;
            } else {
                x.prev.next = x.next;
                x.next.prev = x.prev;
            }
            --size;
        }

        /**
         * 删除链表中最后一个节点，并返回该节点
         *
         * @return 删除的结点
         */
        public LinkedNode removeLast() {
            LinkedNode node = tail;
            remove(tail);
            return node;
        }

        /**
         * 返回链表长度
         *
         * @return 链表长度
         */
        public int size() {
            return size;
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = create(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(2));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(1));
    }
}
